
/*
 *https://leetcode.cn/problems/accounts-merge/ //
 *并查集
*/

#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

// 并查集类
class UnionFind {
public:
    vector<int> parent;  // 父节点数组

    // 构造函数，初始化并查集
    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;  // 初始时每个节点的父节点是自己
        }
    }

    // 合并操作
    void unionSet(int index1, int index2) {
        parent[find(index2)] = find(index1);  // 将 index2 的根节点指向 index1 的根节点
    }

    // 查找操作，带路径压缩
    int find(int index) {
        if (parent[index] != index) {
            parent[index] = find(parent[index]);  // 路径压缩
        }
        return parent[index];
    }
};

// 解决方案类
class Solution {
public:
    // 主函数，合并账户
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        map<string, int> emailToIndex;  // 映射邮箱到索引
        map<string, string> emailToName;  // 映射邮箱到用户名
        int emailCnt = 0;  // 邮箱计数器

        // 1. 记录每个邮箱的索引和对应的用户名
        for (auto& account : accounts) {
            string name = account[0];  // 获取用户名
            for (int i = 1; i < account.size(); i++) {
                string email = account[i];  // 获取邮箱
                if (!emailToIndex.count(email)) {
                    emailToIndex[email] = emailCnt++;  // 为新邮箱分配索引
                    emailToName[email] = name;  // 记录邮箱对应的用户名
                }
            }
        }

        // 2. 使用并查集合并账户
        UnionFind uf(emailCnt);  // 初始化并查集
        for (auto& account : accounts) {
            int firstIndex = emailToIndex[account[1]];  // 获取第一个邮箱的索引
            for (int i = 2; i < account.size(); i++) {
                uf.unionSet(firstIndex, emailToIndex[account[i]]);  // 合并所有邮箱
            }
        }

        // 3. 将每个根节点对应的邮箱合并到一起
        map<int, vector<string>> indexToEmails;  // 映射根节点索引到邮箱列表
        for (auto& [email, index] : emailToIndex) {
            int rootIndex = uf.find(index);  // 找到根节点索引
            indexToEmails[rootIndex].push_back(email);  // 将邮箱添加到对应根节点的列表中
        }

        // 4. 构建最后的结果
        vector<vector<string>> merged;  // 存储合并后的账户
        for (auto& [index, emails] : indexToEmails) {
            sort(emails.begin(), emails.end());  // 按字典序排序邮箱
            string name = emailToName[emails[0]];  // 获取用户名
            vector<string> account;
            account.emplace_back(name);  // 添加用户名
            account.insert(account.end(), emails.begin(), emails.end());  // 添加邮箱
            merged.emplace_back(account);  // 添加到结果中
        }
        return merged;
    }
};
